<!DOCTYPE html>
<html>
<head>
    <style>
        .container {
            width: 800px;
            height: 600px;
            background: #f0f0f0;
            position: relative;
            border-radius: 8px;
            padding: 20px;
            display: flex;
            flex-direction: column;
            align-items: center;
        }
        .tree-container {
            width: 100%;
            height: 400px;
            position: relative;
            margin-top: 20px;
        }
        .node {
            width: 40px;
            height: 40px;
            background: #90CAF9;
            border-radius: 50%;
            display: flex;
            align-items: center;
            justify-content: center;
            position: absolute;
            font-size: 16px;
            color: #333;
            transition: all 0.3s;
            border: 2px solid #1976D2;
        }
        .line {
            position: absolute;
            background: #1976D2;
            height: 2px;
            transform-origin: left center;
            transition: all 0.3s;
        }
        .status {
            margin-top: 30px;
            font-size: 16px;
            color: #333;
            font-family: Arial, sans-serif;
        }
        .target-display {
            margin-top: 20px;
            font-size: 18px;
            color: #333;
            font-family: Arial, sans-serif;
        }
    </style>
</head>
<body style="margin: 0; display: flex; justify-content: center; align-items: center; height: 100vh; background: #f0f0f0;">
    <div class="container">
        <div class="target-display" id="target-display"></div>
        <div class="tree-container" id="tree-container"></div>
        <div class="status" id="status"></div>
    </div>

    <script>
        // 创建二叉搜索树
        class TreeNode {
            constructor(value) {
                this.value = value;
                this.left = null;
                this.right = null;
            }
        }

        // 构建二叉搜索树
        function buildBST(array) {
            let root = null;
            for (let value of array) {
                root = insert(root, value);
            }
            return root;
        }

        function insert(root, value) {
            if (!root) {
                return new TreeNode(value);
            }
            if (value < root.value) {
                root.left = insert(root.left, value);
            } else {
                root.right = insert(root.right, value);
            }
            return root;
        }

        // 创建树的可视化
        function createTree(root, container, x, y, level = 0) {
            if (!root) return;

            const node = document.createElement('div');
            node.className = 'node';
            node.textContent = root.value;
            node.style.left = `${x}px`;
            node.style.top = `${y}px`;
            container.appendChild(node);

            const spacing = 200 / Math.pow(2, level);
            
            if (root.left) {
                const line = document.createElement('div');
                line.className = 'line';
                line.style.left = `${x + 20}px`;
                line.style.top = `${y + 20}px`;
                line.style.width = `${spacing}px`;
                line.style.transform = `rotate(-30deg)`;
                container.appendChild(line);
                createTree(root.left, container, x - spacing, y + 60, level + 1);
            }

            if (root.right) {
                const line = document.createElement('div');
                line.className = 'line';
                line.style.left = `${x + 20}px`;
                line.style.top = `${y + 20}px`;
                line.style.width = `${spacing}px`;
                line.style.transform = `rotate(30deg)`;
                container.appendChild(line);
                createTree(root.right, container, x + spacing, y + 60, level + 1);
            }
        }

        // 更新状态显示
        function updateStatus(message) {
            document.getElementById('status').textContent = message;
        }

        // 树表查找动画
        async function treeSearch(root, target) {
            const nodes = document.querySelectorAll('.node');
            let current = root;
            let path = [];

            while (current) {
                const node = Array.from(nodes).find(n => parseInt(n.textContent) === current.value);
                if (!node) continue;

                // 高亮当前节点
                node.style.backgroundColor = '#FF4081';
                path.push(current.value);
                updateStatus(`检查节点: ${current.value}`);
                await new Promise(resolve => setTimeout(resolve, 1000));

                if (current.value === target) {
                    node.style.backgroundColor = '#4CAF50';
                    updateStatus(`找到目标值 ${target}，路径: ${path.join(' -> ')}`);
                    return;
                } else if (target < current.value) {
                    updateStatus(`${current.value} 大于目标值 ${target}，向左子树查找`);
                    current = current.left;
                } else {
                    updateStatus(`${current.value} 小于目标值 ${target}，向右子树查找`);
                    current = current.right;
                }

                // 重置当前节点的颜色
                node.style.backgroundColor = '#90CAF9';
                await new Promise(resolve => setTimeout(resolve, 1000));
            }

            updateStatus(`未找到目标值 ${target}`);
        }

        // 初始化并开始动画
        function init() {
            const array = [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45, 55, 65, 75, 85];
            const target = array[Math.floor(Math.random() * array.length)];
            const root = buildBST(array);

            // 显示目标值
            document.getElementById('target-display').textContent = `查找目标值: ${target}`;

            // 清空并重新创建树
            const container = document.getElementById('tree-container');
            container.innerHTML = '';
            createTree(root, container, 400, 50);

            // 开始查找动画
            setTimeout(() => treeSearch(root, target), 1000);
        }

        init();

        // 每15秒重置并重新开始
        setInterval(init, 15000);
    </script>
</body>
</html> 